Location based services for mobile stations are expected to play an important role in future applications of wireless systems. A wide variety of technologies for locating mobile stations have been developed. Many of these have been targeted towards the Federal Communication Commission's (“FCC”) requirement to determine the location of emergency 9-1-1 callers with a high degree of accuracy. These technologies may be classified into external methods or network based methods. One example of an external method is the Global Positioning System (“GPS”). Network based methods may be further categorized depending on whether it is the network or the mobile station that performs necessary signal measurements. These signal measurements may involve the reception time of signals communicated between a base station (“BS”) and a mobile station (“MS”), the angle of arriving signals or round trip delay measurements of signals communicated between a serving BS and an MS, or combinations thereof.
Most methods require specific hardware in the MS and/or in the network. Furthermore, Location Measurement Units (“LMU”) are generally required for some methods to obtain knowledge about the relative time differences for sending signals to different mobile stations. As a result, a network operator is faced with a high initial cost for investing in new equipment. Such a disadvantage applies for both network and MS based methods.
For many location based services, it is expected that an accuracy of five hundred meters or even more is sufficient. For these types of services, investments in new expensive equipment is not easily justified. For some cases, a phased solution may be the most attractive choice where a network operator will initially offer services based on low accuracy positioning methods and may later invest in new equipment as revenues increase.
It is thus of interest to investigate what may be done with a minimum of network impact and expense. The currently available network information with respect to MS location includes the identity of the serving cell, timing advance and measurement reports from the MS. The timing advance is an estimate of a signal propagation time and is used for calculating the distance between the serving BS and the MS. MS measurement reports include measurements of the received signal strengths and identities of neighboring BSs as well as those of the serving BS.
Time of Arrival (“TOA”) measurements provide a propagation time of signals between an MS and a BS. Time Difference of Arrival (“TDOA”) measurements provide the difference of signal propagation time of signals between the MS and two different BSs. The measurements of the two BSs may then be used for calculating the actual position of the MS. This procedure, using well-known geometric equations, is commonly called triangulation.
FIG. 1 is an illustration of a TOA measuring procedure. With reference to FIG. 1, a mobile station 110 is capable of communication with at least three base stations 112, 114, 116. In order to determine the position of the MS 110, the distance between the MS 110 and each of the three BSs may be measured using a TOA technique. The measured distance 113 between the base station 112 and the MS 110 defines a circle 103 around the base station 112. The MS 110 is located somewhere on the circle 103. Likewise, the measured distances 115, 117 between the base stations 114, 116 and the MS 110 defines circles 105, 107, respectively, around the base stations 114, 116. The intersection of the circles 103, 105 and 107 defines the location of the MS 110.
In a TDOA measuring technique, the position determinations use TDOA calculations which are further based on TOA measurements. In this method, the position of the MS is located at or near the point where a plurality of hyperbolic arcs cross over one another. The two most common known positioning methods are the Down-Link Observed Time Difference of Arrival method (“DL-OTDOA”) and the Up-link Time of Arrival method (“UL-TOA”). The DL-OTDOA method is generally based on measurements performed by the MS.
FIG. 2 is an illustration of a DL-OTDOA measuring procedure. With reference to FIG. 2, a MS 210 is capable of communication with a serving base station 216 at a distance 217 and further with two neighboring base stations 212, 214 at distances 213, 215 respectively. OTDOAs of downlink signals received from two base stations define a hyperbola, represented by dashed lines. The areas indicated outside the dashed lines represent measurement error margins. When three or more BSs are available, a plurality of hyperbolas may be defined and the MS will be located in the intersection 219 of these hyperbolas. To compensate for any non-time aligned transmissions from the different BSs, the Base Station Time Offsets (“BSTO”) must be known if the BSs are unsynchronized to a global time reference. In conventional systems, BSTOs are generally obtained by employing LMUs in at least some of the BSs. UL-TOA operates in a similar manner, although in this case, the BSs make measurements on uplink signals transmitted by the MS.
The 3GPP standard recommended OTDOA solution involves installing LMUs at each BS in order to measure the BSTOs. This additional hardware requirement introduces a significant cost to network operators interested in utilizing OTDOA for MS location. Universal Mobile Telecommunications System (“UMTS”) operators are currently not implementing OTDOA in either the handsets or the network since the 3GPP standard recommended solution is not cost effective and overly complex. The current focus by UMTS operators is to implement Assisted GPS (“A-GPS”) as the only high-accuracy location method. In the event when A-GPS fails to produce a fix in difficult areas, e.g., indoors and dense urban areas, UMTS operators will not have a reliable fall-back method. This is a disadvantage for UMTS carriers when compared to CDMA carriers employing Advanced Forward Link Trilateration (“AFLT”) that is commonly relied upon as a reliable backup method in the event A-GPS fails. UMTS carriers will thus be required to address this issue once A-GPS begins to be deployed and location based services are offered that require a better yield than A-GPS provides.
Further issues may exist with plural BSs and MSs. For example, a network may comprise unsynchronized BSs in fixed geographical positions with plural MSs having unknown locations. This lack of synchronization manifests itself in unknown time offsets among the transmissions of the BSs. The BSs periodically (or with some known protocol) transmit signals S1 the form of which is known a priori at the MSs. The MSs observe these signals and form OTDOAs of these signals. The OTDOAs are hence families of hyperboloids in space or hyperbolae in two dimensions. Additionally, the BSs transmit other signals S2 which, upon receipt at an MS, trigger the generation of further signals S3 at the MS whose form and timing with respect to the signals S2 is known. The S3 signals then permit the BSs transmitting the signals S2 to determine the Round Trip Time (“RTT”) with respect to the MS.
At any given time one may thus assume that there are some number of MSs in a network reporting the OTDOAs with respect to a subset of BSs in the network. Additionally, the BSs report the RTTs with respect to some subset of MSs in the network. It may then be assumed that all of this OTDOA and RTT data is associated with a time stamp indicating the time of receipt and collected at a device termed a Location Computer that computes MS locations and tracks the BSTOs.
In the absence of BSTOs, it is generally recognized that the location of a single MS may be achieved through the knowledge of multiple OTDOAs with respect to multiple BSs or fewer OTDOAs coupled with RTTs as recommended in 3GPP TS 25.305 version 7.3.0 Rel. 7. There are, however, several issues associated with a direct implementation of the recommendation in this technical standard. First, the BSs are unsynchronized which results in a modification of each OTDOA by an unknown amount equal to the relative time shift between the associated BSs. Thus, the BSTOs are not equal to zero, and may be quite large. Second, the number of practically observable BSs per MS is limited, i.e., there may be very few available OTDOAs. Third, the 3GPP standard recommended OTDOA solution involves installing LMUs in each BS to measure the associated BSTOs. This additional hardware requirement introduces a significant cost to operators interested in using OTDOA for MS location.
Thus, the implementation of the 3GPP standard recommended solution may not be viable unless some method of estimating BSTOs is made available. Once the BSTOs are estimated, however, it may be possible to determine the location of an MS by a single OTDOA and RTT. There is thus a need in the art for estimating BSTOs using OTDOAs and RTTs jointly in a single solution and for estimating BSTOs when available data is highly limited such that the available equations are under-determined, i.e., cases where there are more variables than equations. There is also a need in the art to determine the location of an MS when such under-determined equations exist or when using OTDOAs and RTTs jointly in a single solution.
Accordingly, there is a need for a method and system for estimating the location of a mobile station that receives signals from a plurality of base stations. Therefore, an embodiment of the present subject matter provides a method for estimating the location of a mobile station that receives signals from a plurality of base stations. The method comprises the steps of determining an OTDOA value at a mobile between a first signal received from a first base station and a second signal received from a second base station and determining an RTT value between the mobile and the first base station. The method further comprises selecting an initial location for the mobile that is within a first predetermined area and determining an estimated location for the mobile using the selected initial location, the OTDOA and RTT values, and an iterative search algorithm wherein the iterative search algorithm iterates a predetermined number of steps. If the estimated location is within a second predetermined area, and in such cases where the BSs are not time synchronized, this location may be used to estimate the BSTOs. In addition, if a running estimate of this BSTO has been maintained, the current estimate can be modified to exhibit the new information made available from the most recently derived BSTO estimate. The estimated location may also be stored if the estimated location is within this second predetermined area whereby the preceding steps may then be repeated within a predetermined time interval. A location for the mobile may then be determined from the stored estimated locations and the current best estimate of the BSTO, in a jointly optimal manner. It should be apparent to the reader that this includes the case where there may be no currently available best estimate of the BSTO, in which case the current estimate is also the current best estimate, and where the currently obtained location is computed directly from the current measurements.
In another embodiment of the present subject matter a method is provided for estimating the location of a mobile station that receives signals from a plurality of base stations. The method comprises the steps of determining an OTDOA value at the mobile between a first signal received from a first base station and a second signal received from a second base station, selecting an initial location for the mobile that is within a first predetermined area, and determining an estimated location for the mobile using the selected initial location, the OTDOA value, and an iterative search algorithm wherein the iterative search algorithm iterates a predetermined number of steps. The method further comprises storing the estimated location if the estimated location is within a second predetermined area, updating a running best estimate of the applicable BSTO and repeating the aforementioned steps within a predetermined time interval, and determining a calculated location for the mobile from the stored estimated locations and the current best estimate of the BSTO.
In yet another embodiment of the present subject matter a method is provided for estimating the location of a first mobile station and a second mobile station where each mobile station receives signals from the same plurality of base stations. The method comprises the steps of determining a first OTDOA value at the first mobile between a first signal received from a first base station and a second signal received from a second base station, determining a second OTDOA value at the second mobile between a third signal received from the first base station and a fourth signal received from the second base station, determining a first RTT value between the first mobile and the first base station, and determining a second RTT value between the second mobile and the second base station. The method further comprises the steps of selecting a first initial location for the first mobile that is within a first predetermined area, selecting a second initial location for the second mobile that is within a second predetermined area, and determining a first estimated location for the first mobile and a second estimated location for said second mobile. The estimated locations are determined using the selected initial locations, the first OTDOA value, the second OTDOA value, the first RTT value, the second RTT value, and an iterative search algorithm where the iterative search algorithm iterates a predetermined number of steps. The method further comprises the steps of storing the first estimated location if the first estimated location is within a third predetermined area and storing the second estimated location if the second estimated location is within a fourth predetermined area. In addition, if a running estimate of the BSTOs for each pair of BSs is maintained, these BSTOs are updated to manifest the new information available from the current location estimates for the MSs. The aforementioned steps may be repeated within a predetermined time interval, and a calculated location for the first mobile and a calculated location for the second mobile may be determined from the stored estimated locations and the current estimates of the BSTOs.
In an alternative embodiment of the present subject matter a method is provided for estimating the location of a first mobile station and a second mobile station where each mobile station receives signals from the same plurality of base stations. The method comprises the steps of determining a first OTDOA value at the first mobile between a first signal received from a first base station and a second signal received from a second base station, determining a second OTDOA value at the second mobile between a third signal received from the first base station and a fourth signal received from the second base station, selecting a first initial location for the first mobile that is within a first predetermined area, and selecting a second initial location for the second mobile that is within a second predetermined area. A first and second estimated location may be determined for the first and second mobiles, respectively, using the selected initial locations, the first OTDOA value, the second OTDOA value, and an iterative search algorithm wherein the iterative search algorithm iterates a predetermined number of steps. The method further comprises storing the first estimated location if the first estimated location is within a third predetermined area, storing the second estimated location if the second estimated location is within a fourth predetermined area, and repeating the aforementioned steps within a predetermined time interval. Further, if running estimates of the BSTOs are maintained, these estimates are updated in an optimum manner that includes the most recent information derived from the location estimates. Calculated locations for the first and second mobiles may then be determined from the stored estimated locations and the current best estimate of the BSTOs.
In yet another embodiment of the present subject matter a method is provided for estimating the locations of an integer number M of mobile stations where at least one of such MSs receives signals from at least two of N base stations (N>2). In this configuration, some MSs may receive signals from all BSs and some may receive signals from only a pair of BSs. Each MS receiving signals from any pair of BSs is then capable of generating an OTDOA with respect to such a pair. In addition, some number of MSs may have RTTs with respect to specific BSs. It should be clear to the reader that the above scenario will often be described mathematically by a set of under determined equations where an exact solution for at least some of the MS locations cannot be derived from the current set of OTDOA and RTT measurements. The method for this case then comprises the selection of initial locations in a first set of predetermined areas for each of the MMSs, applying an iterative search algorithm where the algorithm iterates for a predetermined number of steps, and storing the resulting MS locations that are obtained in a second set of predetermined areas. As should be evident, not every MS will generate such a valid location. For those locations that do fall into the second set of predeteremined areas, every BSTO that can be updated using such a location is updated to generate a current best estimate of that BSTO. Since there are multiple MSs available, it is possible that there will be more than one current MS location that may be used to update a particular BSTO estimate. The aforementioned steps may be repeated within a predetermined time interval, and a calculated location for each mobile station may be determined from the stored estimated locations and the current estimates of the BSTOs.
In all of the preceding embodiments, and any of a similar nature that may be envisioned, the selection of the first set of locations for the MSs within a set of predetermined regions may be implemented using other a priori knowledge pertaining to the MSs. This information could include the serving cell or sector, mobile power measurements, mobile traffic density distributions, mobile path profile from stored databases etc., all of which may constrain the initial location. Additionally the same set or a similar set of a priori information may be used to constrain the final algorithm determined location that determines when that location is considered valid and is used to update the current BSTO estimates.
These embodiments and many other objects and advantages thereof will be readily apparent to one skilled in the art to which the invention pertains from a perusal of the claims, the appended drawings, and the following detailed description of the embodiments.